import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
       TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
     static  class Solution {
         public String tree2str(TreeNode root) {
             StringBuilder str = new StringBuilder();
             func(root, str);
             return str.toString();
         }

         /*   public void func(TreeNode root,StringBuilder str) {
                   if(root==null) {
                       return;
                   }
                   str.append(root.val);
                   //左边不为空
                   if(root.left!=null) {
                       str.append('(');
                       //右边不为空（左右都不为空）
                       if(root.right!=null) {
                           func(root.left,str);
                           str.append(')');
                           str.append('(');
                           func(root.right,str);
                           str.append(')');
                       }else {
                           //左边不为空右边为空
                           func(root.left,str);
                       }
                   }else {
                       //左边为空,右边不为空
                       if(root.right!=null) {
                           str.append("()");
                           str.append('(');
                           func(root.right,str);
                           str.append('(');
                       }
                   }
            }*/
         public void func(TreeNode root, StringBuilder str) {
             if (root == null) {
                 return;
             }
             str.append(root.val);
             //左边不为空
             if (root.left != null) {
                 str.append('(');
                 func(root.left, str);
                 str.append(')');
                 if (root.right != null) {
                     str.append('(');
                     func(root.right, str);
                     str.append(')');
                 }
             } else {
                 //左边为空 右边不为空
                 if (root.right != null) {
                     str.append("()");
                     str.append('(');
                     func(root.right, str);
                     str.append(')');
                 }
             }
             //右边不为空

         }

         // 判断一棵树是不是完全二叉树
         boolean isCompleteTree(TreeNode root) {
             Deque<TreeNode> deque = new ArrayDeque<>();
             deque.offer(root);
             while (!deque.isEmpty()) {
                 TreeNode cur = deque.poll();
                 if (cur == null) {
                     break;
                 }
                 deque.offer(cur.left);
                 deque.offer(cur.right);
             }
             while (!deque.isEmpty()) {
                 if (deque.poll() != null) {
                     return false;
                 }
             }
             return true;
         }

         public void preorderTraversal(TreeNode root) {
             Deque<TreeNode> deque = new ArrayDeque<>();
             TreeNode cur=root;
             TreeNode pre=null;
           while (cur!=null||!deque.isEmpty()) {
               while (cur!=null) {
                   deque.push(cur);
                   System.out.print(cur+" ");
                   cur=cur.left;
               }
               pre=deque.pop();
               cur=pre.right;

           }
         }
         public List<Integer> postorderTraversal(TreeNode root) {
             Deque<TreeNode> deque = new ArrayDeque<>();
             TreeNode cur=root;
             TreeNode pre=null;
             TreeNode tmp=null;
             List<Integer> list=new LinkedList<>();
             while (cur!=null||!deque.isEmpty()) {
                 while (cur!=null) {
                     deque.push(cur);
                     cur=cur.left;
                 }
                 pre=deque.peek();
                 if(pre.right==null||pre.right==tmp) {
                     tmp=deque.pop();
                    list.add(tmp.val);
                 }else {
                     cur=pre.right;
                 }
             }
             return list;
         }
         public static void main(String[] args) {
             TreeNode p1=new TreeNode(3);
             Solution solution=new Solution();
             solution.preorderTraversal(p1);
         }
     }
}
